package com.mgq.algorithm.dp;

/**
 * 马跳日  给定(x,y)和step, 计算从(0,0)到(x,y)经过step步,总共多少种方法
 * 从(0,0)到(x,y)和从(x,y)到(0,0)的结果是一样的.
 * 我们使用计算从 从(x,y)到(0,0) 因为最终 (0,0)好表示
 */
public class HorseJump {

    /**
     * process 函数
     *
     * @param x
     * @param y
     * @param step
     * @return
     */
    public static int process(int x, int y, int step) {
        //base case 越界
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            //直接返回0
            return 0;
        }
        //step=0.表示步数用完了,如果返回到了(0,0),说明找到了一种方法
        if (step == 0) {
            return (x == 0 && y == 0) ? 1 : 0;
        }
        //其他情况是8种可能,每种可能步数-1
        return process(x + 1, y + 2, step - 1) +
                process(x - 1, y + 2, step - 1) +
                process(x - 2, y + 1, step - 1) +
                process(x + 2, y + 1, step - 1) +
                process(x - 2, y - 1, step - 1) +
                process(x + 2, y - 1, step - 1) +
                process(x - 1, y - 2, step - 1) +
                process(x + 1, y - 2, step - 1);
    }

    /**
     * dp方式
     *
     * @param x
     * @param y
     * @param step
     * @return
     */
    public static int dp(int x, int y, int step) {
        int[][][] dp = new int[9][10][step + 1];
        if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {
            //直接返回0
            return 0;
        }
        //其他默认就是0, int数组默认值就是0
        dp[0][0][0] = 1;
        for (int i = 1; i <= step; i++) {
            //x 9个位置
            for (int j = 0; j < 9; j++) {
                // y 10个位置
                for (int k = 0; k < 10; k++) {
                    //上一层只和 step有关,和x,y无关. 因为第0层已经计算了, 只依赖i-1.
                    dp[j][k][i] += getValue(dp, j + 1, k + 2, i - 1);
                    dp[j][k][i] += getValue(dp, j - 1, k + 2, i - 1);
                    dp[j][k][i] += getValue(dp, j - 2, k + 1, i - 1);
                    dp[j][k][i] += getValue(dp, j + 2, k + 1, i - 1);
                    dp[j][k][i] += getValue(dp, j - 2, k - 1, i - 1);
                    dp[j][k][i] += getValue(dp, j + 2, k - 1, i - 1);
                    dp[j][k][i] += getValue(dp, j - 1, k - 2, i - 1);
                    dp[j][k][i] += getValue(dp, j + 1, k - 2, i - 1);
                }
            }
        }
        return dp[x][y][step];
    }

    /**
     * 解决越界的问题
     *
     * @param dp
     * @param row
     * @param col
     * @param step
     * @return
     */
    public static int getValue(int[][][] dp, int row, int col, int step) {
        if (row < 0 || row > 8 || col < 0 || col > 9) {
            return 0;
        }
        return dp[row][col][step];

    }

    public static void main(String[] args) {
        System.out.println(process(8, 8, 8));
        System.out.println(dp(8, 8, 8));
    }
}
